// 回文子串个数
/**
 * @param {string} s
 * @return {number}
 */

// 动态规划
var countSubstrings = function (s) {
  let result = 0
  let len = s.length

  let dp = new Array(len)
  for (let i = 0; i < len; i++) {
    dp[i] = new Array(len).fill(false)
  }

  for (let i = len - 1; i >= 0; i--) {
    for (let j = i; j < len; j++) {
      if (s[i] === s[j]) {
        if (j - i <= 1) {
          result++
          dp[i][j] = true
        } else if (dp[i + 1][j - 1] === true) {
          result++
          dp[i][j] = true
        }
      }
    }
  }

  return result
};
console.log(countSubstrings('aaa'));


